package _13_调整数组顺序使奇数位于偶数前面;

import java.util.Arrays;

/**
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
并保证奇数和奇数，偶数和偶数之间的相对位置不变。
 */

/**
 * 思路
 *      先从头找到第一个偶数下标i，再从i开始找第一个奇数下标j，此时不能直接交换，否则顺序会乱
 *      此时进行将从i到j-1的元素往后复制1位覆盖，然后将该奇数放到i的位置
 */
public class Solution {


    public void reOrderArray(int[] array) {

        for (int i = 0; i < array.length; ) {
            while (i < array.length && array[i] % 2 == 1) i++;
            int j = i + 1;
            while (j < array.length && array[j] % 2 == 0) j++;
            if (j < array.length) {
                int tmp = array[j];
                for(int j2=j-1;j2>=i;j2--){
                    array[j2+1] = array[j2];
                }
                array[i] = tmp;
            }
            else {break;}
        }

    }

    public static void main(String[] args) {
        int a[] = {1, 2, 3, 4, 5, 6};
        Solution solution = new Solution();
        solution.reOrderArray(a);
        Arrays.stream(a).forEach(System.out::print);
    }
}
